package com.LeeCode;

import java.util.Arrays;

/**
 * 移动石子直到连续 II
 */

public class Code1040 {
    public static void main(String[] args) {
        int[] stones = {6, 5, 4, 3, 10};
        System.out.println(Arrays.toString(new Code1040().numMovesStonesII(stones)));
    }

    public int[] numMovesStonesII(int[] stones) {
        Arrays.sort(stones);
        int[] ans = new int[2];
        int n = stones.length;

        int leftFree = stones[n - 2] - stones[0] - n + 2;
        int rightFree = stones[n - 1] - stones[1] - n + 2;
        ans[1] = Math.max(leftFree, rightFree);

        if (leftFree == 0 || rightFree == 0) {
            ans[0] = Math.min(2, ans[1]);
            return ans;
        }
        int maxCount = 0, left = 0;

        for (int right = 0; right < n; right++) {
            while (stones[right] - stones[left] + 1 > n) {
                left++;
            }
            maxCount = Math.max(maxCount, right - left + 1);
        }
        ans[0] = n - maxCount;
        return ans;
    }
}
